The key value store is designed to extract values from very large amounts of data and is highly available， fault-tolerant， and scalable， providing a much needed infrastructure to support Location-Based Service （LBS）. However， complex queries on multidimensional data cannot be processed effectively because the key value store does not provide a way to access multiple properties. For the key value storage， HBase cannot effectively deal with the problem of multidimensional data， a uniform indexing framework named New-grid was proposed. In the improved P-grid coverage network， a group of nodes was organized to provide efficient data distribution， fault tolerance and multi-dimensional data query processing. For indexing purposes， the locality of data storage based on Hilbert space filling curves was used to effectively manage the multidimensional data in the key value store. Simultaneously， HBase underlying storage was used to manage data， and an algorithm of range query and K-Nearest Neighbors （KNN） query were given to eliminate the overhead of maintaining separate index tables. Extensive experiments were conducted on Amazon EC2 using cluster sizes of 4， 8 and 16 normal nodes. Experimental results show that New-grid performance is more optimized than MD-HBase and MapReduce.